Time division multiple access (TDMA) is a communications system that divides a single frequency channel into short-duration time slots to enable multiple users to transmit on the same channel.
Hybrid TD—Spread Spectrum (SS) or TDMA-SS transmission systems employ a succession of short-duration PN encoded data bursts emanating from one or more communication stations.
Spread spectrum (SS) systems, which may be CDMA systems, are well known in the art. SS systems can employ a transmission technique in which a pseudo-noise (PN) PN-code is used as a modulating waveform to spread the signal energy over a bandwidth much greater than the signal information bandwidth. At the receiver the signal is de-spread using a synchronized replica of the PN-code.
In general, there are two basic types of SS systems: direct sequence spread spectrum systems (DSSS) and frequency hop spread spectrum systems (FHSS).
The DSSS systems spread the signal over a bandwidth fRF±Rc, where fRF represents the carrier frequency and Rc represents the PN-code chip rate, which in turn may be an integer multiple of the symbol rate Rs. Multiple access systems employ DSSS techniques when transmitting multiple channels over the same frequency bandwidth to multiple receivers, each receiver sharing a common PN code or having its own designated PN-code. Although each receiver receives the entire frequency bandwidth, only the signal with the receiver's matching PN-code will appear intelligible; the rest appears as noise that is easily filtered. These systems are well known in the art and will not be discussed further.
FHSS systems employ a PN-code sequence generated at the modulator that is used in conjunction with an m-ary frequency shift keying (FSK) modulation to shift the carrier frequency fRF at a hopping rate Rh. A FHSS system divides the available bandwidth into N channels and hops between these channels according to the PN-code sequence. At each frequency hop time a PN generator feeds a frequency synthesizer a sequence of n chips that dictates one of 2n frequency positions. The receiver follows the same frequency hop pattern. FHSS systems are also well known in the art and need not be discussed further. In many situations using CDMA or TDMA-SS, particularly military situations, data communications are encrypted by the sender and decrypted by the receiver. Decryption by the receiver requires that the receiver have a decryption key. The key may be private or public.
One method of public-key encryption, developed by Rivest, Shamir & Adelman, and generally referred to as RSA, is based upon the use of two large prime numbers which fulfill the criteria for the “trap-door, one-way permutation.” Such a permutation function enables the sender to encrypt the message using a non-secret encryption key, but does not permit an eavesdropper to decrypt the message by crypto-analytic techniques.
As described in U.S. Pat. No. 4,354,982 to Miller et al., public-key encryption is useful for transmitting periodic changes in encryption keys on open channels. In the public-key encryption method, the need for a master encryption key in which to encrypt the periodic changes of the standard key is avoided. Thus, the need to transmit over a secure channel, or to physically transport the master key by courier or the like, is avoided. Without public-key encryption, each user must have the master key. Though the master key does not change often, as each new user comes on the data encryption line, a master key must be sent in some secure manner to that user. Each such transfer, even over a secure channel or by physical hand delivery, could be compromised, thus necessitating changing the master key for all users.
Public-key encryption enables the standard keys, which change periodically, to be sent over open channels to each user with a publicly known public-key, which though publicly known, is not capable of decryption by anyone other than the individual user.
Generally, the RSA public-key system has the following features. Assuming that the receiver of the message is located at terminal A, terminal A will have first computed two very large random prime numbers p, q. The product of p and q is then computed and constitutes the value n. A large random integer e is then selected which has the property that the greatest common divisor (GCD) of e, and the product of (p−1) and (q−1) is 1. Stated in equation form:GCD[e,(p−1)(q−1)]=1  (Eq. 1A)where: e is a large random integer which is relatively prime to the product of (p−1) and (q−1). An integer d is then computed which is the “multiplicative inverse” of e in modulo (p−1) (q−1):e*d≡1[mod(p−1)(q−1)]  (Eq. 2A).
Terminal A transmits n and e to another terminal, e.g., Terminal B, in clear text without encryption, or a public list of n and e for every terminal, including Terminal A, is made publicly known. Terminal B responds by encrypting and transmitting a message M into an encrypted transmission C as follows:C≡E(M)≡Me (mod n)  (Eq. 3A).
Terminal B then sends the encrypted message C. Terminal A then performs an operation upon the received encoded message C as follows:M=(C)d (mod n)  (Eq. 4A)Due to the properties of the selected large random prime numbers this “open trap-door, one-way permutation” results in the identical message M.
An interceptor who receives, or otherwise knows the publicly transmitted n and e, cannot easily decode the message sent by terminal B without the number d. Thus, the transmission from Terminal B to Terminal A is secure against decryption by unauthorized recipients.
However, as is known in the art, there exists factoring algorithms such as the Schroeppel algorithm, for factoring the number n. For an n of e.g., 50 digits in length, the Schroeppel algorithm can be used to factor n in 3.9 hours, on a large-scale digital computer.
It will be appreciated by those skilled in the art that message security is measured, or determined, by the amount of time it would take an unauthorized user to decrypt a message using techniques such as factoring. A one thousand year period in which to factor the value of n using factoring techniques is generally accepted as completely secure. It will be appreciated therefore, that the random numbers p and q must be extremely large. For the public-key system, the digit length of n is generally one hundred digits; and the corresponding digit length of p and q are each approximately sixty digits. It can be readily understood that generating random prime numbers sixty digits in length requires several hours on commercially available microprocessors.
It is therefore desirable to provide a fast encryption/decryption method and system whereby information may be encrypted/decrypted using public and/or master keys less susceptible to compromise but quickly determined by authorized or intended users.